#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define STACKMAXSIZE 50

typedef int StackElemType;

typedef struct {
	StackElemType elem[STACKMAXSIZE];
	int top;
} SeqStack;

// 初始化
void InitSeqStack(SeqStack *S) {
	S->top = -1;
}

// 入栈
int PushStack(SeqStack *S, StackElemType e) {
	if (S->top >= STACKMAXSIZE - 1) {
		printf("栈满！\n");
		return 0;
	}
	S->elem[++S->top] = e;
	return 1;
}

// 出栈
int PopStack(SeqStack *S, StackElemType *e) {
	if (S->top < 0) {
		printf("栈空！\n");
		return 0;
	}
	*e = S->elem[S->top--];
	return 1;
}

// 获取栈顶元素
int GetTop(SeqStack *S, StackElemType *e) {
	if (S->top < 0) {
		printf("栈空！\n");
		return 0;
	}
	*e = S->elem[S->top];
	return 1;
}

// 操作符优先级
int Priority(char op) {
	switch (op) {
		case '#': return 0;
		case '(': return 1;
	case '+':
		case '-': return 3;
	case '*':
		case '/': return 5;
		case '^': return 7;
		default: return -1;
	}
}

// 表达式求值
int ExpEvaluation(char *str) {
	SeqStack opStack, numStack;
	InitSeqStack(&opStack);
	InitSeqStack(&numStack);
	PushStack(&opStack, '#');
	char op;
	
	int i = 0;
	while (str[i] != '#' || opStack.elem[opStack.top] != '#') {
		if (str[i] >= '0' && str[i] <= '9') {
			int num = 0;
			while (str[i] >= '0' && str[i] <= '9') {
				num = num * 10 + (str[i] - '0');
				i++;
			}
			PushStack(&numStack, num);
		} else {
			switch (str[i]) {
				case '(': PushStack(&opStack, str[i]); i++; break;
				case ')': 
				while (opStack.elem[opStack.top] != '(') {
					int v1, v2, result;
					PopStack(&opStack, &op);
					PopStack(&numStack, &v2);
					PopStack(&numStack, &v1);
					switch (op) {
						case '+': result = v1 + v2; break;
						case '-': result = v1 - v2; break;
						case '*': result = v1 * v2; break;
						case '/': result = v1 / v2; break;
						case '^': result = (int)pow(v1, v2); break;
					}
					PushStack(&numStack, result);
				}
				PopStack(&opStack, &op); // 弹出 '('
				i++;
				break;
			default:
				while (Priority(opStack.elem[opStack.top]) >= Priority(str[i])) {
					int v1, v2, result;
					PopStack(&opStack, &op);
					PopStack(&numStack, &v2);
					PopStack(&numStack, &v1);
					switch (op) {
						case '+': result = v1 + v2; break;
						case '-': result = v1 - v2; break;
						case '*': result = v1 * v2; break;
						case '/': result = v1 / v2; break;
						case '^': result = (int)pow(v1, v2); break;
					}
					PushStack(&numStack, result);
				}
				PushStack(&opStack, str[i]);
				i++;
				break;
			}
		}
	}
	int result;
	PopStack(&numStack, &result);
	return result;
}

int main() {
	int v;
	char str[80];
	printf("输入一个表达式，以#为结束！\n");
	fgets(str, sizeof(str), stdin);
	str[strcspn(str, "\n")] = 0; // 移除换行符
	strcat(str, "#"); // 添加结束标志
	v = ExpEvaluation(str);
	printf("该表达式的运算结果为：%d\n", v);
	return 0;
}
